#include<iostream>
#include<vector>
#include <unordered_set>
using namespace std;
/*
给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。
注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。
解题思路：
题目能够转化为给定一个容量为s的背包，用wordDict物品去装满这个背包，故能够转化为完全背包类问题
设dp[j]表示容量为j的背包能否用wordDict中的物品能否被装满（true或false）
设i>j,则当dp[j]=true时，从j-i的一段一定有wordDict中存在与之对应的字符串才能使得dp[i]==true
故有递推公式：dp[i]=（wordDict.find(s.substr(j,i-j))!=wordDict.end()&&dp[j]==true）
*/
int dp(string s,vector<string> wordDict)
{
    //添加一个元素唯一的集合但是不保证元素顺序
    unordered_set<string> wordSet(wordDict.begin(), wordDict.end());
    //创建dp数组并进行初始化 
    vector<bool> dp(s.size()+1);
    //一定要将dp[0]初始化为true不然后面递推全部为false
    dp[0] = true;
    //由于本题强调单词间的顺序，故应该是求排列数，所以要先遍历背包后遍历物品
    for(int i=1;i<=s.size();i++)
    {
        //注意内层循环应该如何去遍历物品，根据递推公式j应该小于i
        //所以要从j开始截取j-i长度的str，判断是否在wordDict中
        for(int j=0;j<i;j++)
        {
            //截取s中的一段字符串
            string str = s.substr(j,i-j);
            if(wordSet.find(str)!=wordSet.end()&&dp[j]==true)
                dp[i] = true;
        }
    }
    return dp[s.size()];
}
int main()
{
    cout<<"enter s:"<<endl;
    string s;
    cin>>s;
    cout<<"enter a number:"<<endl;
    int number;
    cin>>number;
    cout<<"enter wordDict:"<<endl;
    vector<string> wordDict(number);
    for(int i=0;i<number;i++)
    {
        cin>>wordDict[i];
    }
    if(dp(s,wordDict))
        cout<<"true"<<endl;
    else
        cout<<"false"<<endl;
    return 0;
}